#!/usr/bin/python3

import unicodedata

#Char constants
#Used in char classes
CONST_HYPHEN =      '-'
CONST_BSLASH =      '\\'
CONST_CARROT =      '^'
CONST_LBRACKET =    '['
CONST_RBRACKET =    ']'
CONST_STAR =        '*'

class CC_Rule():
    pass
class CC_RuleSingleChar(CC_Rule):
    def __init__(self, c):
        self.c = c
#class CC_RuleNegChar(CC_Rule):
    #def __init__(self, c):
        #self.c = c
class CC_RuleRange(CC_Rule):
    def __init__(self, beg, end):
        assert(beg < end)
        self.beg = beg
        self.end = end

#--Node Types--
class RE_Node:
    """def addChild(self, child):
        if self.n_children == 0:
            self.n1 = child
        elif self.n_children == 1:
            self.n2 = child
        else:
            assert self.n_children > 0
            raise RuntimeError('Too many children')"""
    def __init__(self):
        self.n1 = None; self.n2 = None
    def __repr__(self):
        return self.__class__.__name__
    def printout(self, nind):
        print(' '*nind + repr(self))
        if self.n1 != None:
            self.n1.printout(nind+2)
        if self.n2 != None:
            self.n2.printout(nind+2)

#Either a symbol or char class
class RE_NodePrimitive(RE_Node):
    pass
class RE_Symbol(RE_NodePrimitive):
    def __init__(self, sym):
        super().__init__()
        assert len(sym) == 1
        self.sym = sym
    def __repr__(self):
        return self.__class__.__name__ + '(' + self.sym + ')'
class RE_CharClass(RE_NodePrimitive):
    def __init__(self, cctxt):
        #self.text = cctxt
        self.rules = []
        self.is_neg = False
        self.l = findClosingBracket(cctxt)
        self.parseText(cctxt)
    def parseText(self, text):
        #text = str(arg_text) #make a copy because input is consumed
        if lremaining() < 1:
            raise RuntimeError('RE_CharClass.parseText: Empty character class')
        #Entire class will be negated if there is a leading ^
        if text[0] == CONST_CARROT:
            self.is_neg = True
            consume(text)
        else:
            self.is_neg = False
        #Get first char
        curChar = getChar(text)
        if lremaining() > 0:
            moreChars = True
        else:
            moreChars = False
        while moreChars:
            #See if this is a range
            if text[0] == CONST_HYPHEN:
                consume(text)
                if lremaining() == 0:
                    #Can add hyphen at end of class - I think it's a bad idea
                    self.addRule(CC_RuleSingleChar(CONST_HYPHEN))
                    return
                #Get other end
                rhs = getChar(text)
                self.addRule(CC_RuleRange(curChar,rhs))
                curChar = rhs
            else:
                self.addRule(CC_RuleSingleChar(curChar))
                curChar = getChar(text)
        
    def getChar(text, debug_text=None):
        if lremaining() < 1:
            raise RuntimeError('RE_CharClass.getChar: Empty character class')
        if text[0] == CONST_HYPHEN:
            raise RuntimeError('RE_CharClass.getChar: Unexpected hyphen in ' + str(debug_text))
        elif text[0] == CONST_BSLASH:
            assert( lremaining() > 2)
            consume(text)
            if text[0] == CONST_BSLASH:
                consume(text)
                return CONST_BSLASH
            elif text[0] == CONST_HYPHEN:
                consume(text)
                return CONST_HYPHEN
            elif text[0] == CONST_CARROT:
                consume(text)
                return CONST_CARROT
            else:
                raise RuntimeError('RE_CharClass.getChar: Invalid escape sequence in character class: ' + str(debug_text))
        elif text[0] == CONST_CARROT:
            #This is okay - carrot has regular meaning after first column
            consume(text)
            return text[0]
        else:
            #Any non-escaped symbol
            consume(text)
            return text[0]
        
    def consume(text):
        text = text[1:]
        
    def addRule(self, rule):
        self.rules.append(rule)
        
    def lremaining(self):
        return self.l
    
    def findClosingBracket(s):
        r = s.find(CONST_RBRACKET)
        assert r >= 0
        if r > 0:
            while s[r-1] == CONST_BSLASH:
                assert len(s) > r
                r = s.find(CONST_RBRACKET, r+1)
                assert r > 0
        return r

#Unary Op
class RE_UnaryOp(RE_Node):
    pass
#Negation
class RE_Neg(RE_UnaryOp):
    pass
#*
class KleeneClosure(RE_UnaryOp):
    pass

#BinaryOp
class RE_BinaryOp(RE_Node):
    pass
    """def __init__(self, n1, n2):
        assert issubclass(n1, RE_Node), issubclass(n2, RE_Node)
        self.n1 = n1
        self.n2 = n2"""
#Concatenation
class RE_BinConcat(RE_BinaryOp):
    prec = 10
#+
class RE_BinOr(RE_BinaryOp):
    prec = 20
#&
class RE_BinAnd(RE_BinaryOp):
    prec = 30

#RE Operations
#Bin
REOP_CONCAT = RE_BinConcat
REOP_OR = RE_BinOr
REOP_AND = RE_BinAnd
#Unary
REOP_KCLOSURE = KleeneClosure

#Root node
class RE_Root(RE_Node):
    prec = 100

#Tree
class RE_Tree:
    def __init__(self):
        pass

#Forms:
LEFT_CANONICAL_FORM = 'LEFT_CANONICAL_FORM'
RIGHT_CANONICAL_FORM = 'RIGHT_CANONICAL_FORM'

class FA:
    #self.n is a new candidate node
    #--State handlers:--
    def StateStart(self, c, w):
        print('Entered start state')
        if(c == CONST_LBRACKET):
            #Character class
            print('Parsing char class')
            if self.form == RIGHT_CANONICAL_FORM:
                self.n = RE_CharClass(w)
            else:
                self.p = RE_CharClass(w)
                self.setAsChildn1(self.p, self.root)
            self.statep = type(self).StatePostPrim
        elif c==CONST_STAR:
            raise RuntimeError('Unexpected character encountered in stream: ' + c)
        else:
            #Single char
            print('Parsing single char ' + c)
            if self.form == RIGHT_CANONICAL_FORM:
                self.n = RE_Symbol(c)
            else:
                self.p = RE_Symbol(c)
                self.setAsChildn1(self.p, self.root)
            self.statep = type(self).StatePostPrim
        return w
            
    def StatePostPrim(self, c, w):
        if(c == CONST_LBRACKET):
            #Character class
            print('Parsing char class')
            nnew = RE_CharClass(w)
            #join via concatenation
            self.join_binop(nnew, REOP_CONCAT, type(REOP_CONCAT).prec)
            self.statep = type(self).StatePostPrim
            return w
        elif c==CONST_STAR:
            raise RuntimeError('Unexpected character encountered in stream: ' + c)
        else:
            #Single char
            print('Parsing single char ' + c)
            nnew = RE_Symbol(c)
            #join via concatenation
            self.join_binop(nnew, REOP_CONCAT, REOP_CONCAT.prec)
            self.statep = type(self).StatePostPrim
            return w
        
    def StateDead(self, c, w):
        raise RuntimeError('Dead state')
    #Tree construction
    def join_binop(self, nnew, op, op_prec):
        if self.current_prec == None:
            self.current_prec = op_prec
        if self.insertAsChild:
            print('Binop: ' + op.__name__ + ' -> (' + repr(self.n) + ', ' + repr(nnew) + ')')
            if(op_prec <= self.current_prec):
                #Action for equal or lower prec:
                self.setAsChildn2(op(), self.p) #add new node
                self.p = self.p.n2 #reset ph
                self.setAsChildn1(self.n, self.p)
                self.n = nnew
            else:
                #this terminates the branch
                setAsChildn2(self.n, self.p)
                while type(self.p.parent).prec <= self.current_prec:
                    self.p = self.p.parent
                brokenBranch = self.p
                #insert new op here
                o = insertOp()
                self.setAsChildn2(o, self.p.parent)
                self.setAsChildn1(brokenBranch, o)
                self.n = nnew
                self.p = o
        else:
            o = op()
            setAsChildn1(self.p, o)
            setAsChildn2(nnew, o)
            self.p = o
    def insertOp(self, op):
        #insert at self.p
        o = op()
        setAsChildn1(self.p.n2, o)
        setAsChildn2(o, self.p)
    def setAsChildn1(self, node, parent):
        parent.n1 = node
        node.parent = parent
    def setAsChildn2(self, node, parent):
        parent.n2 = node
        node.parent = parent
    #Mechanics
    def __init__(self):
        self.statep = type(self).StateStart
        self.accept_flag = False
        self.ast = RE_Tree()
        self.form = RIGHT_CANONICAL_FORM
        self.current_prec = None
        if self.form == RIGHT_CANONICAL_FORM:
            self.insertAsChild = True
        else:
            self.insertAsChild = False
    def run(self, w):
        if self.form == RIGHT_CANONICAL_FORM:
            self.root = RE_Root()
            self.p = self.root
        while len(w) > 0:
            w = self.statep(self, *self.nextToken(w))
        if self.form == RIGHT_CANONICAL_FORM:
            #place last child
            self.setAsChildn2(self.n, self.p)
        print('Finished')
        return self.root
        
    def nextToken(self, w): #consumes input
        t = self.getToken(w)
        w = self.consume(w)
        return (t, w)
    def getToken(self, w):
        return w[0]
    def consume(self, b):
        assert len(b) > 0
        return b[1:]

fa = FA()

#fa.run(unicode('aab*'))
r = fa.run('ab')
r.printout(0)
